#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 1e5+10;

int h[N<<1],cnt,cc[N],siz[N<<1],nodenum,lst,k,n;
char s[N];
struct edge{int v,nxt;}e[N<<1];
void link(int x,int y){e[++cnt] = (edge){y,h[x]};h[x] = cnt;}
struct suff{int len,link,ch[26];}t[N<<1];

void add(int c){
	int cur = ++nodenum,p = lst; lst = cur; t[cur].len = t[p].len + 1; siz[cur]++;
	while(p && !t[p].ch[c]) t[p].ch[c] = cur,p = t[p].link;
	if(!p) return t[cur].link = 1,void();
	int q = t[p].ch[c]; if(t[p].len + 1 == t[q].len) return t[cur].link = q,void();
	int clo = ++nodenum; t[clo].link = t[q].link; for(int i = 0;i < 26;i++) t[clo].ch[i] = t[q].ch[i]; t[clo].len = t[p].len + 1;
	while(p && t[p].ch[c] == q) t[p].ch[c] = clo,p = t[p].link;
	t[q].link = t[cur].link = clo;
}

void dfs(int x){for(int i = h[x],y;i;i = e[i].nxt) dfs(y = e[i].v),siz[x] += siz[y];}

void solve(){
	scanf("%s",s+1); k = in; n = strlen(s+1); lst = 1;
	for(int i = 1;i <= nodenum;i++) t[i].link = t[i].len = 0,memset(t[i].ch,0,sizeof(t[i].ch)),h[i] = 0,cc[i] = 0,siz[i] = 0;
	cnt = 0; nodenum = 1; 
	for(int i = 1;i <= n;i++) add(s[i]-'a');
	for(int i = 2;i <= nodenum;i++) link(t[i].link,i);
	dfs(1);
	for(int i = 2;i <= nodenum;i++)
		if(siz[i] == k) cc[t[t[i].link].len+1]++,cc[t[i].len+1]--;
	for(int i = 1;i <= n+1;i++) cc[i] += cc[i-1];
	int ans = 0;
	for(int i = 1;i <= n;i++)
		if(cc[i] >= cc[ans]) ans = i;
	if(!cc[ans]) ans = -1;
	printf("%d\n",ans);
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	int T = in;while(T--) solve();
	return 0;
}

